/**
 * //A transformation sequence from word beginWord to word endWord using a
 * //dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
 * //
 * //
 * //
 * // Every adjacent pair of words differs by a single letter.
 * // Every si for 1 <= i <= k is in wordList. Note that beginWord does not need
 * //to be in wordList.
 * // sk == endWord
 * //
 * //
 * // Given two words, beginWord and endWord, and a dictionary wordList, return
 * //all the shortest transformation sequences from beginWord to endWord, or an empty
 * //list if no such sequence exists. Each sequence should be returned as a list of
 * //the words [beginWord, s1, s2, ..., sk].
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog",
 * //"lot","log","cog"]
 * //Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * //Explanation: There are 2 shortest transformation sequences:
 * //"hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * //"hit" -> "hot" -> "lot" -> "log" -> "cog"
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog",
 * //"lot","log"]
 * //Output: []
 * //Explanation: The endWord "cog" is not in wordList, therefore there is no
 * //valid transformation sequence.
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= beginWord.length <= 5
 * // endWord.length == beginWord.length
 * // 1 <= wordList.length <= 500
 * // wordList[i].length == beginWord.length
 * // beginWord, endWord, and wordList[i] consist of lowercase English letters.
 * // beginWord != endWord
 * // All the words in wordList are unique.
 * //
 * //
 * // Related Topics 广度优先搜索 哈希表 字符串 回溯 👍 591 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.*;

public class ID00126WordLadderIi {
    public static void main(String[] args) {

        Solution solution = new ID00126WordLadderIi().new Solution();
        System.out.println(solution.findLadders("cet", "ism", Arrays.asList("kid", "tag", "pup", "ail", "tun", "woo", "erg", "luz", "brr", "gay", "sip", "kay", "per", "val", "mes", "ohs", "now", "boa", "cet", "pal", "bar", "die", "war", "hay", "eco", "pub", "lob", "rue", "fry", "lit", "rex", "jan", "cot", "bid", "ali", "pay", "col", "gum", "ger", "row", "won", "dan", "rum", "fad", "tut", "sag", "yip", "sui", "ark", "has", "zip", "fez", "own", "ump", "dis", "ads", "max", "jaw", "out", "btu", "ana", "gap", "cry", "led", "abe", "box", "ore", "pig", "fie", "toy", "fat", "cal", "lie", "noh", "sew", "ono", "tam", "flu", "mgm", "ply", "awe", "pry", "tit", "tie", "yet", "too", "tax", "jim", "san", "pan", "map", "ski", "ova", "wed", "non", "wac", "nut", "why", "bye", "lye", "oct", "old", "fin", "feb", "chi", "sap", "owl", "log", "tod", "dot", "bow", "fob", "for", "joe", "ivy", "fan", "age", "fax", "hip", "jib", "mel", "hus", "sob", "ifs", "tab", "ara", "dab", "jag", "jar", "arm", "lot", "tom", "sax", "tex", "yum", "pei", "wen", "wry", "ire", "irk", "far", "mew", "wit", "doe", "gas", "rte", "ian", "pot", "ask", "wag", "hag", "amy", "nag", "ron", "soy", "gin", "don", "tug", "fay", "vic", "boo", "nam", "ave", "buy", "sop", "but", "orb", "fen", "paw", "his", "sub", "bob", "yea", "oft", "inn", "rod", "yam", "pew", "web", "hod", "hun", "gyp", "wei", "wis", "rob", "gad", "pie", "mon", "dog", "bib", "rub", "ere", "dig", "era", "cat", "fox", "bee", "mod", "day", "apr", "vie", "nev", "jam", "pam", "new", "aye", "ani", "and", "ibm", "yap", "can", "pyx", "tar", "kin", "fog", "hum", "pip", "cup", "dye", "lyx", "jog", "nun", "par", "wan", "fey", "bus", "oak", "bad", "ats", "set", "qom", "vat", "eat", "pus", "rev", "axe", "ion", "six", "ila", "lao", "mom", "mas", "pro", "few", "opt", "poe", "art", "ash", "oar", "cap", "lop", "may", "shy", "rid", "bat", "sum", "rim", "fee", "bmw", "sky", "maj", "hue", "thy", "ava", "rap", "den", "fla", "auk", "cox", "ibo", "hey", "saw", "vim", "sec", "ltd", "you", "its", "tat", "dew", "eva", "tog", "ram", "let", "see", "zit", "maw", "nix", "ate", "gig", "rep", "owe", "ind", "hog", "eve", "sam", "zoo", "any", "dow", "cod", "bed", "vet", "ham", "sis", "hex", "via", "fir", "nod", "mao", "aug", "mum", "hoe", "bah", "hal", "keg", "hew", "zed", "tow", "gog", "ass", "dem", "who", "bet", "gos", "son", "ear", "spy", "kit", "boy", "due", "sen", "oaf", "mix", "hep", "fur", "ada", "bin", "nil", "mia", "ewe", "hit", "fix", "sad", "rib", "eye", "hop", "haw", "wax", "mid", "tad", "ken", "wad", "rye", "pap", "bog", "gut", "ito", "woe", "our", "ado", "sin", "mad", "ray", "hon", "roy", "dip", "hen", "iva", "lug", "asp", "hui", "yak", "bay", "poi", "yep", "bun", "try", "lad", "elm", "nat", "wyo", "gym", "dug", "toe", "dee", "wig", "sly", "rip", "geo", "cog", "pas", "zen", "odd", "nan", "lay", "pod", "fit", "hem", "joy", "bum", "rio", "yon", "dec", "leg", "put", "sue", "dim", "pet", "yaw", "nub", "bit", "bur", "sid", "sun", "oil", "red", "doc", "moe", "caw", "eel", "dix", "cub", "end", "gem", "off", "yew", "hug", "pop", "tub", "sgt", "lid", "pun", "ton", "sol", "din", "yup", "jab", "pea", "bug", "gag", "mil", "jig", "hub", "low", "did", "tin", "get", "gte", "sox", "lei", "mig", "fig", "lon", "use", "ban", "flo", "nov", "jut", "bag", "mir", "sty", "lap", "two", "ins", "con", "ant", "net", "tux", "ode", "stu", "mug", "cad", "nap", "gun", "fop", "tot", "sow", "sal", "sic", "ted", "wot", "del", "imp", "cob", "way", "ann", "tan", "mci", "job", "wet", "ism", "err", "him", "all", "pad", "hah", "hie", "aim")));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        HashSet<String> visited = null;

        List<List<String>> allShortestPaths = new ArrayList<>();

        int mininumPathSize = Integer.MAX_VALUE;

        HashSet<String> wordSet = new HashSet<>();
        Map<String, Set<String>> rootMap = new HashMap<>();

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

            wordSet.addAll(wordList);
            if (!wordSet.contains(endWord)) {
                return Collections.emptyList();
            }

//            visited = new HashSet<>();
//            visited.add(beginWord);
            //回溯
//            List<String> tmpPath = new ArrayList<>();
//            tmpPath.add(beginWord);
//            backTracking(beginWord, endWord, tmpPath);


//            BFS(beginWord,endWord,wordSet);

            boolean found = BFS2(beginWord, endWord, wordSet);
            if (found) {
                Deque<String> path = new ArrayDeque<>();
                path.add(endWord);
                findRootPath(beginWord, endWord, path, rootMap);
            }


            return allShortestPaths;
        }

        public void findRootPath(String beginWord, String currWord, Deque<String> path, Map<String, Set<String>> rootMap) {
            if (currWord.equals(beginWord)) {
                allShortestPaths.add(new ArrayList<>(path));
                return;
            }

            for (String rootWord : rootMap.get(currWord)) { //找到所有的root
                path.addFirst(rootWord); //前面加rootWord
                findRootPath(beginWord, rootWord, path, rootMap);//网上找
                path.removeFirst(); //换个根，继续
            }


        }


        public boolean BFS2(String beginWord, String endWord, Set<String> wordSet) {


            int wordLength = beginWord.length();
            HashMap<String, Integer> stepMap = new HashMap<>();
            int step = 0;
            stepMap.put(beginWord, step);

            boolean founded = false;
            wordSet.remove(beginWord);

            Queue<String> nextStringQueue = new LinkedList<>();
            nextStringQueue.offer(beginWord);

            while (!nextStringQueue.isEmpty()) {
                int stepSize = nextStringQueue.size();
                HashSet<String> nextLevelRemoved = new HashSet<>();
                step++;//jump to nextLevel
                for (int i = 0; i < stepSize; i++) {
                    String thisLevelString = nextStringQueue.poll();
                    //不用这个是因为removeAll要比remove一层慢好几步
//                    List<String> neighbour = getAllNeighbor(thisLevelString, wordSet);

                    for (int k = 0; k < wordLength; ++k) {
                        char[] tChar = thisLevelString.toCharArray();
                        char tmp = tChar[k];
                        for (char j = 'a'; j <= 'z'; j++) {

                            if (tmp != j) {
                                tChar[k] = j;
                                String nextLevelString = new String(tChar);
                                if (stepMap.containsKey(nextLevelString) && stepMap.get(nextLevelString) == step) { //说明上一层有两个单词能够汇入这一个词的情况
                                    rootMap.get(nextLevelString).add(thisLevelString); //再次发现此节点，在此节点中的父节点添加当前节点
                                }

                                if (!wordSet.contains(nextLevelString)) {
                                    continue;
                                }

                                stepMap.put(nextLevelString, step);
                                rootMap.putIfAbsent(nextLevelString, new HashSet<>());
                                rootMap.get(nextLevelString).add(thisLevelString);
//                                nextLevelRemoved.add(nextLevelString);
                                wordSet.remove(nextLevelString); //用来当visited)
                                nextStringQueue.offer(nextLevelString); //用来遍历下一层
                                if (nextLevelString.equals(endWord))
                                    founded = true; //停止访问下一层, BFS找到说明当前层就是最短路径，继续往后找一层没有意义了

                            }


                        }

                        tChar[k] = tmp;
                    }


                }


                if (founded) break;


            }


            return founded;


        }


        public void BFS(String beingWord, String endWord, Set<String> wordSet) {

            Queue<List<String>> pathQueue = new LinkedList<>(); //用来保存所有路径

            List<String> startList = new ArrayList<>();
            startList.add(beingWord);
            pathQueue.offer(startList);

            visited.add(beingWord);

            boolean founded = false;

            while (!pathQueue.isEmpty()) {
                int stepSize = pathQueue.size();
                Set<String> nextStepVisited = new HashSet<>();
                for (int i = 0; i < stepSize; i++) {
                    List<String> thisPath = pathQueue.poll();
                    //每次取出当前路径最后一个节点来遍历新一层的neighbor
                    String lastWord = thisPath.get(thisPath.size() - 1);
                    List<String> neighbor = getAllNeighbor(lastWord, wordSet);
                    for (String nextNode : neighbor) {
                        if (!visited.contains(nextNode)) { //这层节点没被遍历过
                            nextStepVisited.add(nextNode);
                            thisPath.add(nextNode);
                            pathQueue.add(new ArrayList<>(thisPath));
                            thisPath.remove(thisPath.size() - 1); //防止后面还有，退回到上一层
                        } else {
                            //节点已经在之前的路径上出现过,或者在同级其他路径出现过，拿就跳过,不用再从这个节点走了
                            continue;
                        }

                        if (endWord.equals(nextNode)) {
                            thisPath.add(nextNode);
                            allShortestPaths.add(new ArrayList<>(thisPath));
                            founded = true;
                            break; //分析下条路经,这条已经找到了
                        }

                    }
                }
                visited.addAll(nextStepVisited);
                //本层节点的下一层遍历结束，如果找到了，就没必要找再远的path了
                if (founded) break;

            }


        }


        public void backTracking(String thisWord, String endWord, List<String> tmpPath) {

            if (tmpPath.size() > mininumPathSize) return; //递归超过最小步数了

            if (thisWord.equals(endWord)) {
                if (tmpPath.size() < mininumPathSize) {
                    mininumPathSize = tmpPath.size(); //当前最小
                    allShortestPaths.clear();
                }
                allShortestPaths.add(new ArrayList<>(tmpPath)); //快照
                return;
            }

            for (int i = 0; i < thisWord.length(); ++i) {
                char[] tChar = thisWord.toCharArray();
                int tmp = tChar[i];
                for (char j = 'a'; j <= 'z'; j++) {

                    if (tmp != j) {
                        tChar[i] = j;
                        String nextWord = new String(tChar);
                        if (!visited.contains(nextWord) && wordSet.contains(nextWord)) {
                            visited.add(nextWord);
                            tmpPath.add(nextWord);

                            backTracking(nextWord, endWord, tmpPath);

                            tmpPath.remove(tmpPath.size() - 1); //减去最后一个
                            visited.remove(nextWord);
                        }
                    }


                }


            }


        }


        /*
         * @Desc: 获取所有BFS邻居节点
         */
        public List<String> getAllNeighbor(String thisWord, Set<String> wordSet) {
            HashSet<String> neighborSet = new HashSet<>();
            for (int i = 0; i < thisWord.length(); ++i) {
                char[] tChar = thisWord.toCharArray();
                int tmp = tChar[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    if (tmp != j) {
                        tChar[i] = j; //修改成下个字符a-z
                        String nextWord = new String(tChar);
                        if (wordSet.contains(nextWord)) {
                            neighborSet.add(nextWord);
                        }
                    }
                }
            }
            return new ArrayList<>(neighborSet);
        }

        public List<String> findPath(String lastWord, Map<String, String> pathMap) {
            List<String> path = new ArrayList<>();
            if (pathMap.get(lastWord) == null) {
                path.add(lastWord);
                return path;
            }
            String root = pathMap.get(lastWord);
            path.addAll(findPath(root, pathMap)); //先添加root
            path.add(lastWord); //再添加自己

            return path;

        }

        /*
         * @Desc: Every adjacent pair of words differs by a single letter.
         */
        public boolean ableToJump(String thisWord, String nextWord) {
            int differentCount = 0;
            char[] thisWordChar = thisWord.toCharArray();
            char[] nextWordChar = nextWord.toCharArray();

            for (int i = 0; i < thisWord.length(); i++) {
                if (thisWordChar[i] != nextWordChar[i]) {
                    differentCount++;
                }
                if (differentCount == 2) {
                    return false;
                }

            }
            return differentCount == 1;

        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}